package com.cg.leetcode;

import org.junit.Test;

/**
 * 1267.统计参与通信的服务器
 *
 * @program: LeetCode->LeetCode_1267
 * @author: cg
 * @create: 2022-04-11 16:58
 **/
public class LeetCode_1267 {

    @Test
    public void test1267() {
        System.out.println(countServers(new int[][]{
                {1, 1, 0, 0},
                {0, 0, 1, 0},
                {0, 0, 1, 0},
                {0, 0, 0, 1}
        }));
        System.out.println(countServers(new int[][]{
                {1, 0},
                {0, 1},
        }));
        System.out.println(countServers(new int[][]{
                {1, 0},
                {1, 1},
        }));
    }

    /**
     * 这里有一幅服务器分布图，服务器的位置标识在 m * n 的整数矩阵网格 grid 中，1 表示单元格上有服务器，0 表示没有。
     * <p>
     * 如果两台服务器位于同一行或者同一列，我们就认为它们之间可以进行通信。
     * <p>
     * 请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。
     * <p>
     * 示例 1：
     * 输入：grid = [[1,0],[0,1]]
     * 输出：0
     * 解释：没有一台服务器能与其他服务器进行通信。
     * <p>
     * 示例 2：
     * 输入：grid = [[1,0],[1,1]]
     * 输出：3
     * 解释：所有这些服务器都至少可以与一台别的服务器进行通信。
     * <p>
     * 示例 3：
     * 输入：grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
     * 输出：4
     * 解释：第一行的两台服务器互相通信，第三列的两台服务器互相通信，但右下角的服务器无法与其他服务器通信。
     * <p>
     * 提示：
     * m == grid.length
     * n == grid[i].length
     * 1 <= m <= 250
     * 1 <= n <= 250
     * grid[i][j] == 0 or 1
     *
     * @param grid
     * @return
     */
    public int countServers(int[][] grid) {
        int res = 0;
        // 记录是否已统计
        int[][] visited = new int[grid.length][grid[0].length];
        // 统计行
        for (int i = 0; i < grid.length; i++) {
            int count = 0;
            for (int j = 0; j < grid[i].length; j++) {
                // 统计一行中服务器的数量
                if (grid[i][j] == 1) {
                    count++;
                    // 标记该行
                    visited[i][j] = 1;
                }
            }
            if (count > 1) {
                // 2台以上，记录数量
                res += count;
            } else {
                // 清楚标记
                visited[i] = new int[visited[i].length];
            }
        }
        // 统计列
        for (int i = 0; i < grid[0].length; i++) {
            int count = 0;
            int visit = 0;
            for (int j = 0; j < grid.length; j++) {
                // 统计一列中服务器数量
                if (grid[j][i] == 1) {
                    count++;
                    if (visited[j][i] == 1) {
                        // 已经标记过，计数
                        visit++;
                    } else {
                        // 没有则进行标记
                        visited[j][i] = 1;
                    }
                }
            }
            if (count > 1) {
                // 两台以上, 减去已统计的
                res += (count - visit);
            }
        }
        return res;
    }

}
